#ifndef	__BFX_LIST_H__
#define	__BFX_LIST_H__

namespace	BFX
{
template<typename TYPE>
class BFX_TMPL List
{
public:
	typedef const TYPE& ARG_TYPE;

	typedef struct Entry
	{
		TYPE	value;
	protected:
		Entry(ARG_TYPE val) : value(val) {}
	} * POSITION;

protected:
	struct Node : public Entry, virtual public REFObject
	{
		// Construct a new node.
		Node(ARG_TYPE value, Node* pPrev, Node* pNext, const List* pContainer)
			: Entry(value)
		{
			this->pPrev = pPrev;
			this->pNext = pNext;
			this->pContainer = pContainer;
		}
		Node*		pPrev;
		REF<Node>	pNext;
		const List* pContainer;
	};

public:
	List()
	{
		m_pLast = NULL;
		m_nSize = 0;
	}
	virtual ~List()
	{
	}

	// Adding before or after a given position
	POSITION AddBefore(POSITION pos, ARG_TYPE value)
	{
		if (pos == NULL)
			AddFirst(value);	 // insert before NULL -> head of the list

		// Insert it before position
		Node* pOldNode = (Node*) pos;
		BFX_ASSERT(pOldNode->pContainer == this);
		Node* pNewNode = new Node(value, pOldNode->pPrev, pOldNode, this);
		if (pOldNode->pPrev != NULL)
		{
			pOldNode->pPrev->pNext = pNewNode;
		}
		else
		{
			BFX_ASSERT(m_pFirst == pOldNode);
			m_pFirst = pNewNode;
		}
		pOldNode->pPrev = pNewNode;
		return (POSITION) pNewNode;
	}
	POSITION AddAfter(POSITION pos, ARG_TYPE value)
	{
		if (pos == NULL)
			AddLast(value);

		// Insert it after position
		Node* pOldNode = (Node*) pos;
		Node* pNewNode = new Node(value, pOldNode, pOldNode->pNext, this);
		if (pOldNode->pNext != NULL)
		{
			pOldNode->pNext->pPrev = pNewNode;
		}
		else
		{
			BFX_ASSERT(m_pLast == pOldNode);
			m_pLast = pNewNode;
		}
		pOldNode->pNext = pNewNode;
		return (POSITION) pos;
	}
	// Add first or last
	POSITION AddFirst(ARG_TYPE value)
	{
		Node* pNewNode = new Node(value, NULL, m_pFirst, this);
		if (m_pFirst != NULL)
		{
			BFX_ASSERT(m_pLast != NULL);
			m_pFirst->pPrev = pNewNode;
		}
		else
		{
			BFX_ASSERT(m_pLast == NULL);
			m_pLast = pNewNode;
		}
		m_pFirst = pNewNode;
		m_nSize ++;
		return pNewNode;
	}
	POSITION AddLast(ARG_TYPE value)
	{
		Node* pNewNode = new Node(value, m_pLast, NULL, this);
		if (m_pLast != NULL)
		{
			BFX_ASSERT(m_pFirst != NULL);
			m_pLast->pNext = pNewNode;
		}
		else
		{
			BFX_ASSERT(m_pFirst == NULL);
			m_pFirst = pNewNode;
		}
		m_pLast = pNewNode;
		m_nSize ++;
		return pNewNode;
	}
	// Get first or last, and remove it.
	void RemoveFirst()
	{
		if (m_pFirst == NULL)
			return;

		REF<Node> pHolder = m_pFirst;	// NOTE: hold the node to prevent release too early.

		m_pFirst = m_pFirst->pNext;
		if (m_pFirst != NULL)
		{
			m_pFirst->pPrev = NULL;
		}
		else
		{
			m_pLast = NULL;
		}
		m_nSize --;
	}
	void RemoveLast()
	{
		if (m_pLast == NULL)
			return;

		m_pLast = m_pLast->pPrev;
		if (m_pLast != NULL)
		{
			m_pLast->pNext = NULL;
		}
		else
		{
			m_pFirst = NULL;
		}
		m_nSize --;
	}
	// Remove an object at given position
	void RemoveAt(POSITION pos)
	{
		if (pos == NULL)
			return;

		REF<Node> pHolder = m_pFirst;	// NOTE: hold the node to prevent release too early.

		REF<Node> pOldNode = (Node*) pos;
		BFX_ASSERT(pOldNode->pContainer == this);

		if (pOldNode == m_pFirst)
		{
			m_pFirst = pOldNode->pNext;
		}
		else
		{
			pOldNode->pPrev->pNext = pOldNode->pNext;
		}
		if (pOldNode == m_pLast)
		{
			m_pLast = pOldNode->pPrev;
		}
		else
		{
			pOldNode->pNext->pPrev = pOldNode->pPrev;
		}
		m_nSize --;
	}
	// Remove an given object
	void Remove(ARG_TYPE value)
	{
		POSITION pos = Find(value);
		if (pos != NULL)
		{
			RemoveAt(pos);
		}
	}
	// Remove all objects
	void Clear()
	{
		m_pFirst = m_pLast = NULL;
		m_nSize = 0;
	}

	// Find functions (note: O(n) speed)
	POSITION Find(ARG_TYPE value) const
	{
		for (Node* pNode = m_pFirst; pNode != NULL; pNode = pNode->pNext)
		{
			if (pNode->value == value)
				return (POSITION) pNode;
		}
		return NULL;
	}
	POSITION FindRev(ARG_TYPE value) const
	{
		for (Node* pNode = m_pLast; pNode != NULL; pNode = pNode->pPrev)
		{
			if (pNode->value == value)
				return (POSITION) pNode;
		}
		return NULL;
	}
	bool Contains(ARG_TYPE value) const
	{
		return (Find(value) != NULL);
	}

	// Returns the number of objects currently in the list.
	int GetSize() const
	{
		return m_nSize;
	}

	// Getting/modifying an object at given position
	ARG_TYPE GetAt(POSITION pos) const
	{
		BFX_ASSERT (pos != NULL);

		Node* pNode = (Node*) pos;
		BFX_ASSERT(pNode->pContainer == this);

		return pNode->value;
	}
	void SetAt(POSITION pos, ARG_TYPE value)
	{
		BFX_ASSERT (pos != NULL);

		Node* pNode = (Node*) pos;
		BFX_ASSERT(pNode->pContainer == this);
		pNode->value = value;
	}

	// Returns the first/last object.
	ARG_TYPE GetFirst() const
	{
		BFX_ASSERT(m_pFirst != NULL);
		return m_pFirst->value;
	}
	ARG_TYPE GetLast() const
	{
		BFX_ASSERT(m_pLast != NULL);
		return m_pLast->value;
	}

	// Iteration helpers
	POSITION GetFirstEntry() const
	{
		return (POSITION) m_pFirst;
	}
	POSITION GetLastEntry() const
	{
		return (POSITION) m_pLast;
	}
	POSITION GetPrevEntry(POSITION pos) const
	{
		if (pos == NULL)
			return NULL;

		Node* pNode = (Node*) pos;
		BFX_ASSERT(pNode->pContainer == this);
		return pNode->pPrev;
	}
	POSITION GetNextEntry(POSITION pos) const
	{
		if (pos == NULL)
			return NULL;

		Node* pNode = (Node*) pos;
		BFX_ASSERT(pNode->pContainer == this);
		return pNode->pNext;
	}

	private:
#ifdef	_MSC_VER
#pragma warning(push)
#pragma warning(disable:4251)
#endif	//	_MSC_VER
	REF<Node>	m_pFirst;
#ifdef	_MSC_VER
#pragma warning(pop)
#endif	//	_MSC_VER
	Node*		m_pLast;
	int			m_nSize;
};

};	//	namespace BFX

#endif	//	__BFX_LIST_H__
